In a communications chip, a lot of queues usually need to be processed. The queue data is generally stored in an independent off-chip memory and managed in the form of a linked list data structure. The linked list control information may be independently stored in a synchronous static random access memory (SSRAM) that can be accessed at a high speed. The queue data may be stored in a large-capacity synchronous dynamic random access memory (SDRAM) where parallel operations are allowed.
The structure of the queue data is managed by using the header/tail pointer as the main information. The process of dequeuing the data may include the following steps:
(1) Receiving a dequeue command indicating that one or more packets are dequeued. The total amount of dequeue data is equal to “credit” bytes.
(2) Reading a linked list unit pointed to by the “header”, and updating the “header” with the next linked list unit address “nxt_pd_ptr” in the read linked list unit.
(3) Subtracting the data length of the “info” in the read linked list unit from the “credit” bytes. If the remaining amount of bytes “credit” is greater than 0, data that needs to be dequeued still exists. Then, repeat step (2) until the remaining amount of bytes “credit” is smaller than or equal to 0, so as to finish dequeuing.
During the implementation of the present invention, the inventor discovers at least the following problems in the prior art:
In the preceding process, the data corresponding to the node of the next linked list unit can start to be dequeued only after a next pointer of the linked list unit pointed to by the queue header is read. The dependence in operation from the front to the back restricts the dequeue performance and reduces the dequeue efficiency.